#define DEBUG
#include <cstdio>
#include <cstring>
#define INF 0x7ffffff
#define MAXN 1500000

using namespace std;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

class SegmentTree {
public:
  int v[4*MAXN+1], mark[4*MAXN+1];

  void markDown(int o, int l, int r) {
    if (mark[o]) {

      v[o] += mark[o];
      if (l!=r) {
	mark[o*2]+=mark[o];
	mark[o*2+1]+=mark[o];
      }
      mark[o]=0;
    }
  }

  void add(int o, int l, int r, int tl, int tr, int tv) {
    markDown(o, l, r);
    if (l==tl && r==tr) {
      mark[o]+=tv;
      markDown(o, l, r);
    } else {
      int mid=(l+r)/2;
      if (tl<=mid && tr>=l) {
	add(o*2, l, mid, max(tl, l), min(tr, mid), tv);
      }
      if (tl<=r && tr>mid) {
	add(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r), tv);
      }
      v[o] = max(v[o*2], v[o*2+1]);
    }
  }

  int get(int o, int l, int r, int tl, int tr) {
    markDown(o, l, r);
    if (l==tl && r==tr) {
      return v[o];
    } else {
      int ret=0, mid=(l+r)/2;
      if (tl<=mid && tr>=l) {
	ret=max(ret, get(o*2, l, mid, max(tl, l), min(tr, mid)));
      }
      if (tl<=r && tr>mid) {
	ret=max(ret, get(o*2+1, mid+1, r, max(tl, mid+1), min(tr, r)));
      }
      return ret;
    }
  }
};

void sort(int a[][3], int l, int r) {
  int i=l, j=r, mid=a[(l+r)/2][2], temp;
  for (; i<=j; ) {
    for (; a[j][2]>mid; j--);
    for (; a[i][2]<mid; i++);
    if (i<=j) {
      for (int k=0; k<3; k++) {
	temp=a[i][k], a[i][k]=a[j][k], a[j][k]=temp;
      }
      i++, j--;
    }
  }
  if (i<r) {
    sort(a, i, r);
  }
  if (j>l) {
    sort(a, l, j);
  }
}

int main() {
  freopen("exchange.in", "r", stdin);
  freopen("exchange.out", "w", stdout);

  static SegmentTree sgt;
  static int a[MAXN+1], fa[MAXN+1], farthest_son[MAXN+1], ques[MAXN+1][3], ans[MAXN+1], que[MAXN+1][2];
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i=1; i<=n; i++) {
    scanf("%d", a+i);
  }

  int size_que=0;
  for (int i=n; i>0; i--) {
    for (; size_que>0 && que[size_que][0]<=a[i]; size_que--);
    fa[i] = size_que ? que[size_que][1] : i;
    farthest_son[i] = farthest_son[fa[i]] = i;
    que[++size_que][0]=a[i];
    que[size_que][1]=i;
  }
  for (int i=1; i<=n; i++) {
    farthest_son[fa[i]]=min(farthest_son[fa[i]], farthest_son[i]);
  }

  for (int i=1; i<=m; i++) {
    scanf("%d %d", ques[i]+1, ques[i]+2);
    ques[i][0] = i;
  }
  sort(ques, 1, m);

  for (int i=1, j=1; i<=m; i++) {
    for (; j<=ques[i][2]; j++) {
      sgt.add(1, 1, n, farthest_son[j], j, 1);
    }
    ans[ques[i][0]] = sgt.get(1, 1, n, ques[i][1], ques[i][2]);
  }

  for (int i=1; i<=m; i++) {
    printf("%d\n", ans[i]);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
